<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 选择一个基准值，比这个值大的放到left,比这个值小的放到右边
      function quickSort(arr) {
        if (arr.length <= 1) {
          // 说明已经排好序
          return arr;
        }
        let mainIndex = Math.floor((arr.length - 1) / 2);
        let mainItem = arr.splice(mainIndex, 1)[0];
        let left = [];
        let right = [];
        arr.forEach((item) => {
          if (item > mainItem) {
            right.push(item);
          } else {
            left.push(item);
          }
        });
        return quickSort(left).concat([mainItem], quickSort(right));
      }
      console.log(quickSort([1, 4, 5, 7, 8, 9, 6, 100, 99]));
    </script>
  </body>
</html>
